#define __STDC_WANT_LIB_EXT1__ 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define BUF_LEN 256												//Input buffer length
#define INIT_NSTR 2												//Initial number of strings
#define NSTR_INCR 2												//Incremnet to number of strings

char* str_in();													//Reads a string
void str_sort(const char**, size_t);							//Sorts an array of strings
void swap(const char**,const char**);							//Swaps two pointers
void str_out(const char* const*,size_t);						//Outputs the strings
void free_memory(char **,size_t);								//Free all heap memory


//Function main - execution starts here
int main(int argc, char const *argv[])
{
	size_t pS_size = INIT_NSTR;									//count of pS elements
	char **pS = malloc(pS_size*sizeof(char*));					//Array of string pointers
	if(!pS){
		printf("Failed to allocate memory for string pointers.\n");
		exit(1);
	}
	char **pTemp = NULL;										//Temporary pointer

	size_t str_count = 0;										//Number of strings read
	char *pStr = NULL;											//String pointer
	printf("Enter one string per line. Press Enter to end:\n");
	while((pStr = str_in()) !=NULL){
		if(str_count == pS_size){
			pS_size += NSTR_INCR;
			if(!(pTemp = realloc(pS,pS_size*sizeof(char*)))){
				printf("Memory allocation for array of string failed.\n");
				return 2;
			}
			pS = pTemp;
		}

		pS[str_count++] = pStr;
	}
	str_sort(pS,str_count);										//Sort strings
	str_out(pS,str_count);										//Output strings
	free_memory(pS,str_count);									//Free all heap memory
	return 0;
}

/**
字符串通过str_in()从键盘上读取
返回类型是char*，即指向字符串的指针。  
字符串读入本地数组buf中，然后再在堆上分配足够的内存，其地址存储在本地变量pString中。  
buf中的字符串复制到堆内存中，返回pString中存储的地址。
*/
char* str_in(void){
	char buf[BUF_LEN];											//Space to store input string
	// if(!gets_s(buf,BUF_LEN)){								//If NULL returned..
	// 	printf("\nError reading string.\n");					//...end the operation
	// 	return NULL;
	// }
	// if(buf[0]=='\0')											//If empty string read...
	// 	return NULL;											//...end the operation
	fgets(buf,BUF_LEN,stdin);	
	if(buf[0]=='\n')
		return NULL;

	size_t str_len = strnlen(buf,BUF_LEN)+1;
	char *pString = malloc(str_len);

	if(!pString){												//If no memory allocated...
		printf("Memory allocation failure.\n");
		return NULL;											//...end the operation
	}

	strcpy(pString,buf);										//Copy string read to new memory
	return pString;
}

/**
冒泡排序来给字符串排序。
第一个参数是const char**类型，即指向const char*的指针。这是一个指向字符串的指针数组，其中字符串是常量，但其地址不是常量。因此可以交换地址从而达到排序。  
注意，不是修改字符串，也不是修改字符串的地址。而是修改指针数组中的指针的值。
*/
void str_sort(const char **p, size_t n){
	bool sorted = false;										//Strings sorted indicator
	while(!sorted){
		sorted = true;											//Initialize to indicate no swaps
		for (int i = 0; i < n-1; ++i)
		{
			if(strcmp(p[i],p[i+1]) > 0){
				sorted = false;									//indicate we are out of order
				swap(&p[i],&p[i+1]);							//Swap the string addresses
			}
		}
	}
}

/**
哇，这个函数的理解很重要。为什么要使用这样的参数类型和这样的临时变量类型。  
变元时按值传递的，所以必须把变量的地址传递给函数，函数才能修改调用函数中的值。
swap()函数的变元是&p[i]和&p[i+1]，它们是p[i]和p[i+1]的地址，即（指向这些元素的）指针。
而这些元素是什么类型？它们是指向（const char的指针）的指针，这指针的类型const char*。  
综上所述，swap()函数的参数类型const char**，即（指向const char的指针）的指针。
在这里如果参数类型定义中仅仅只使用了一个*，且使用p[i]和p[i+1]作为变元，函数就会收到包含这些元素中的字符串。
const char**与const char*[]类型相同，后者是const char*类型的数组。可以写任意一种，但不能写成const char*[] p1。
如果理解了使用这些参数类型的原因，则它们的内容是const char*类型，则临时变量pT也是使用这个类型。
*/
void swap(const char** p1,const char** p2){
	const char *pT = *p1;
	*p1 = *p2;
	*p2 = pT;
}

/**
第一个参数是const char* const*类型，它是（指向const char的const指针）的指针。
*/
void str_out(const char* const* pStr,size_t n){
	printf("The sorted strings are:\n");
	for(size_t i=0;i<n;i++){
		printf("%s", pStr[i]);
	}
}

void free_memory(char **pS,size_t n){
	for(size_t i=0;i<n;i++){
		free(pS[i]);
		pS[i] = NULL;
	}

	free(pS);
	pS = NULL;
}